/*
 * @lc app=leetcode.cn id=198 lang=java
 *
 * [198] 打家劫舍
 */

// @lc code=start
class Solution {
    public int rob(int[] nums) {

        /* solution 1
        int[][] dp = new int[nums.length + 1][2];

        //0 -> rob
        //1 -> not rob

        for (int i = 1; i < nums.length + 1; i++) {
            dp[i][0] = dp[i - 1][1] + nums[i - 1];
            dp[i][1] = Math.max(dp[i - 1][0], dp[i -1][1]);
        }

        return Math.max(dp[nums.length][0], dp[nums.length][1]);
        */

        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);
        int res = dp[1];

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
            res = Math.max(dp[i], res);
        }

        return res;
    }
}
// @lc code=end

